package com.jojo.intermediate.day11_linkedList;

import com.jojo.elementary.entity.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * 160、相交链表
 *
 * 给你两个单链表的头节点headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
 *
 * 进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？
 */
public class IntersectList {

    /** myCode 哈希表 */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();
        while (headA != null || headB != null){
            if (headA != null){
                if(!set.add(headA)){
                    return headA;
                }
                headA = headA.next;
            }
            if (headB != null){
                if(!set.add(headB)){
                    return headB;
                }
                headB = headB.next;
            }
        }
        return null;
    }

    /** myCode 哈希表 */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if (headA == null || headB == null){
            return null;
        }
        ListNode curA = headA;
        ListNode curB = headB;
        while (curA != null || curB != null){
           if (curA == null){
               curA = headB;
           }
           if (curB == null){
               curB = headA;
           }
           if (curA == curB){
               return curA;
           }
           curA = curA.next;
           curB = curB.next;
        }
        return null;
    }
}
